package com.gxc.string;

/**
 * 44. 通配符匹配
 * 给你一个输入字符串 (s) 和一个字符模式 (p) ，请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：
 * '?' 可以匹配任何单个字符。
 * '*' 可以匹配任意字符序列（包括空字符序列）。
 * 判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）
 */
public class IsMatch2 {

    public static void main(String[] args) {
        System.out.println(dp2("aa", "a"));
        System.out.println(dp2("aa", "*"));
        System.out.println(dp2("cb", "?a"));
        System.out.println(dp2("aa", "aa"));
        //System.out.println(dp("acdcb", "a*c?b"));
        System.out.println(dp2("acdcb", "a*c?b"));
    }

    /**
     * 递归判断
     * s  0.....i
     * p  o.....j  是否匹配
     * @param s
     * @param p
     * @return
     */
    private static boolean handle(String s, String p) {
        return recursion(s, p , 0, 0);
    }

    private static boolean recursion(String s, String p, int i, int j) {
        if (i == s.length() && j == p.length()) return true;
        if (i == s.length() && j != p.length()) {
            for (int k = j; k < p.length(); k++) {
                if (p.charAt(k) != '*') return false;
            }
            return true;
        }
        if (i != s.length() && j == p.length()) return false;

        if (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i)) return recursion(s, p, i+1, j+1);
        else if (p.charAt(j) == '*') {
            //j 匹配i 后 尝试匹配 i+1
            //j 匹配i 后 j=1 尝试匹配 i+1
            //j 不匹配i  j=1 尝试匹配 i+1
            return recursion(s, p, i+1, j) || recursion(s, p, i+1, j+1) || recursion(s, p, i, j+1);
        } else {
            return false;
        }
    }

    /**
     * dp
     * @param s
     * @param p
     * @return
     */
    private static boolean dp(String s, String p) {
        int ls = s.length();
        int lp = p.length();
        boolean[][] dp = new boolean[ls+1][lp+1];
        dp[0][0] = true;
        for (int i = 0; i <= ls; i++) {
            for (int j = 1; j <= lp; j++) {
                if (p.charAt(j-1) == '*'){
                    // * 参与匹配
                    if (i>0) dp[i][j] = dp[i-1][j];
                    // * 不参与匹配
                    dp[i][j] = dp[i][j-1] || dp[i][j];
                } else if (p.charAt(j-1) == '?'){
                    if (i>0) {
                        dp[i][j] = dp[i-1][j-1];
                    }
                } else if (i>0 && p.charAt(j-1) == s.charAt(i-1)) {
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }
        return dp[ls][lp];
    }

    /**
     * 节省空间
     * 使用滚动数组对空间进行优化，即用两个长度为 n+1 的一维数组代替整个二维数组进行状态转移
     * （数组的状态需要重置）
     * @param s
     * @param p
     * @return
     */
    private static boolean dp2(String s, String p) {
        int ls = s.length();
        int lp = p.length();
        boolean[] last = new boolean[lp+1];
        boolean[] cur = new boolean[lp+1];
        last[0] = true;
        for (int i = 0; i <= ls; i++) {
            if (i == 0) {
                cur[0] = true;
            } else {
                cur[0] = false;
            }
            for (int j = 1; j <= lp; j++) {
                if (p.charAt(j-1) == '*'){
                    // * 参与匹配
                    if (i>0) cur[j] = last[j];
                    // * 不参与匹配
                    cur[j] = cur[j-1] || cur[j];
                } else if (p.charAt(j-1) == '?'){
                    if (i>0) {
                        cur[j] = last[j-1];
                    }
                } else if (i>0 && p.charAt(j-1) == s.charAt(i-1)) {
                    cur[j] = last[j-1];
                } else {
                    cur[j] = false;
                }
            }
            for (int k = 0; k < cur.length; k++) {
                last[k] = cur[k];
            }
        }
        return cur[lp];
    }

    /**
     * 贪心算法
     */
    class Solution {
        public boolean isMatch(String s, String p) {
            int sRight = s.length(), pRight = p.length();
            while (sRight > 0 && pRight > 0 && p.charAt(pRight - 1) != '*') {
                if (charMatch(s.charAt(sRight - 1), p.charAt(pRight - 1))) {
                    --sRight;
                    --pRight;
                } else {
                    return false;
                }
            }

            if (pRight == 0) {
                return sRight == 0;
            }

            int sIndex = 0, pIndex = 0;
            int sRecord = -1, pRecord = -1;

            while (sIndex < sRight && pIndex < pRight) {
                if (p.charAt(pIndex) == '*') {
                    ++pIndex;
                    sRecord = sIndex;
                    pRecord = pIndex;
                } else if (charMatch(s.charAt(sIndex), p.charAt(pIndex))) {
                    ++sIndex;
                    ++pIndex;
                } else if (sRecord != -1 && sRecord + 1 < sRight) {
                    ++sRecord;
                    sIndex = sRecord;
                    pIndex = pRecord;
                } else {
                    return false;
                }
            }

            return allStars(p, pIndex, pRight);
        }

        public boolean allStars(String str, int left, int right) {
            for (int i = left; i < right; ++i) {
                if (str.charAt(i) != '*') {
                    return false;
                }
            }
            return true;
        }

        public boolean charMatch(char u, char v) {
            return u == v || v == '?';
        }
    }
}
